#include <bits/stdc++.h>

#define int unsigned
#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

inline char nc(){
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
template < typename T > T read() {
	T x = 0; char ch = nc();
	while(!isdigit(ch)) ch = nc();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = nc();
	return x;
}
char obuf[1<<23],*O=obuf;
void print(ll x) {
    if(x>9) print(x/10);
    *O++=x%10+'0';
}
template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 5e5 + 10;

int vpot[N * 800], *cur = vpot;
int *pot[N], *fa[N];
int n, m, cnt[N], tcnt[N];
signed mx, a[N];
ll tr[N];
inline void add(signed x, const signed &v) { for(; x <= n; x += x & -x) tr[x] += v; }
inline ll query(signed x) { ll res = 0; for(; x; x ^= x & -x) res += tr[x]; return res; }

signed main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	n = in, m = in; rep(i, 1, n) a[i] = in, chkmax(mx, a[i]), ++cnt[a[i]];
	rep(i, 2, mx) {
		pot[i] = cur; int tot = 1;
		rep(j, i, mx) {
			tot += cnt[j];
			j += i - 1;
		}
		cur += tot + 10; fa[i] = cur; cur += tot + 10;
	}
	rep(i, 1, n) {
		int x = a[i], l = sqrt(x);
		rep(j, 1, l) {
			if(x % j) continue;
			if(j > 1) pot[j][tcnt[j]++] = i;
			if(x / j > 1 && j * j != x) pot[x / j][tcnt[x / j]++] = i;
		} add(i, x);
	}
	rep(i, 2, mx) {
		pot[i][tcnt[i]++] = n + 1;
		iota(fa[i], fa[i] + tcnt[i], 0);
	} ll ans = 0;
	while(m--) {
		int op = in; ll l = lin ^ ans, r = lin ^ ans, x;
		if(op == 1) {
			x = lin ^ ans; if(x == 1 || x > mx) continue;
			int *pot = ::pot[x], *fa = ::fa[x];
			const auto &gf = [&](const int &x) {
								 function<int(const int&)> tgf;
								 tgf = [&](int x){ return fa[x] == x ? x : fa[x] = tgf(fa[x]); };
								 return tgf(x);
							 };
			int pos = lower_bound(pot, pot + tcnt[x], l) - pot;
			while(pot[pos = gf(pos)] <= r) {
				if(a[pot[pos]] % x == 0) add(pot[pos], a[pot[pos]] / x - a[pot[pos]]), a[pot[pos]] /= x;
				if(a[pot[pos]] % x != 0) fa[pos] = pos + 1;
				pos++;
			}
		} else print(ans = query(r) - query(l - 1)), *O++ = '\n';
	}
	fwrite(obuf,O-obuf,1,stdout);
	return 0;
}
